/*
 * 字符串算法模板库 - 高效的字符串处理算法
 * 使用场景: 字符串匹配、查找、分析等问题
 * 包含: KMP、Z算法、Manacher、字符串哈希、后缀数组等
 */

#pragma once
#include "basic_template.hpp"

// KMP算法 - 高效的字符串匹配算法
// 使用场景: 在文本中查找模式串的所有出现位置
// 时间复杂度: O(n + m)，n为文本长度，m为模式串长度
// 典型应用: 文本搜索、DNA序列匹配、编译器词法分析
// 优点: 线性时间复杂度，避免了朴素算法的回溯
class KMP
{
private:
    vector<int> lps;
    string pattern;

    void compute_lps()
    {
        int m = pattern.length();
        lps.assign(m, 0);
        int len = 0, i = 1;

        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }

public:
    KMP(const string &pat) : pattern(pat)
    {
        compute_lps();
    }

    vector<int> search(const string &text)
    {
        vector<int> result;
        int n = text.length(), m = pattern.length();
        int i = 0, j = 0;

        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }

            if (j == m) {
                result.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return result;
    }

    int count_occurrences(const string &text)
    {
        return search(text).size();
    }
};

// Z算法 - 计算字符串每个位置与前缀的最长公共前缀
// 使用场景: 字符串匹配、周期性检测、前缀分析
// 时间复杂度: O(n)，线性时间算法
// 典型应用: 字符串匹配、回文检测、字符串压缩
// 优点: 实现简单，常数较小，适合竞赛使用
vector<int> z_algorithm(const string &s)
{
    int n = s.length();
    vector<int> z(n);
    int l = 0, r = 0;

    for (int i = 1; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }

        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

// Manacher算法 (最长回文子串) - 线性时间找最长回文子串
// 使用场景: 回文串相关问题，如最长回文子串、回文串计数
// 时间复杂度: O(n)，线性时间算法
// 典型应用: 最长回文子串、回文串判断、字符串美化
// 特点: 同时处理奇偶长度回文串，避免分类讨论
// 注意: 这是一个相对复杂的算法，适合高级竞赛题目
class Manacher
{
private:
    string preprocess(const string &s)
    {
        string result = "#";
        for (char c : s) {
            result += c;
            result += "#";
        }
        return result;
    }

public:
    vector<int> manacher(const string &s)
    {
        string processed = preprocess(s);
        int n = processed.length();
        vector<int> p(n, 0);
        int center = 0, right = 0;

        for (int i = 0; i < n; ++i) {
            int mirror = 2 * center - i;

            if (i < right) {
                p[i] = min(right - i, p[mirror]);
            }

            while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
                   processed[i + p[i] + 1] == processed[i - p[i] - 1]) {
                p[i]++;
            }

            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }

        return p;
    }

    string longest_palindrome(const string &s)
    {
        vector<int> p = manacher(s);
        int max_len = 0, center_index = 0;

        for (int i = 0; i < p.size(); ++i) {
            if (p[i] > max_len) {
                max_len = p[i];
                center_index = i;
            }
        }

        int start = (center_index - max_len) / 2;
        return s.substr(start, max_len);
    }
};

// 字符串哈希
class StringHash
{
private:
    static const ll BASE = 31;
    static const ll MOD = 1e9 + 7;
    vector<ll> hash_val, power;

public:
    StringHash(const string &s)
    {
        int n = s.length();
        hash_val.resize(n + 1);
        power.resize(n + 1);

        power[0] = 1;
        for (int i = 1; i <= n; ++i) {
            power[i] = (power[i - 1] * BASE) % MOD;
        }

        hash_val[0] = 0;
        for (int i = 1; i <= n; ++i) {
            hash_val[i] = (hash_val[i - 1] * BASE + s[i - 1]) % MOD;
        }
    }

    ll get_hash(int l, int r)
    { // [l, r) 0-indexed
        ll result = hash_val[r] - (hash_val[l] * power[r - l]) % MOD;
        return (result % MOD + MOD) % MOD;
    }

    bool equal(int l1, int r1, int l2, int r2)
    {
        return get_hash(l1, r1) == get_hash(l2, r2);
    }
};

// 后缀数组
class SuffixArray
{
private:
    vector<int> sa, rank, lcp;
    string s;

    void build_sa()
    {
        int n = s.length();
        sa.resize(n);
        rank.resize(n);

        // 初始化
        for (int i = 0; i < n; ++i) {
            sa[i] = i;
            rank[i] = s[i];
        }

        for (int k = 1; k < n; k <<= 1) {
            sort(sa.begin(), sa.end(), [&](int i, int j) {
                if (rank[i] != rank[j])
                    return rank[i] < rank[j];
                int ri = (i + k < n) ? rank[i + k] : -1;
                int rj = (j + k < n) ? rank[j + k] : -1;
                return ri < rj;
            });

            vector<int> new_rank(n);
            new_rank[sa[0]] = 0;
            for (int i = 1; i < n; ++i) {
                new_rank[sa[i]] = new_rank[sa[i - 1]];
                if (rank[sa[i - 1]] < rank[sa[i]] ||
                    (rank[sa[i - 1]] == rank[sa[i]] &&
                     ((sa[i - 1] + k < n ? rank[sa[i - 1] + k] : -1) <
                      (sa[i] + k < n ? rank[sa[i] + k] : -1)))) {
                    new_rank[sa[i]]++;
                }
            }
            rank = new_rank;
        }
    }

    void build_lcp()
    {
        int n = s.length();
        lcp.resize(n - 1);
        vector<int> inv_sa(n);

        for (int i = 0; i < n; ++i) {
            inv_sa[sa[i]] = i;
        }

        int h = 0;
        for (int i = 0; i < n; ++i) {
            if (inv_sa[i] > 0) {
                int j = sa[inv_sa[i] - 1];
                while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
                    h++;
                }
                lcp[inv_sa[i] - 1] = h;
                if (h > 0)
                    h--;
            }
        }
    }

public:
    SuffixArray(const string &str) : s(str)
    {
        build_sa();
        build_lcp();
    }

    const vector<int> &get_sa() const { return sa; }
    const vector<int> &get_lcp() const { return lcp; }

    // 查找子串的位置范围
    pair<int, int> find_range(const string &pattern)
    {
        int left = lower_bound(sa.begin(), sa.end(), pattern,
                               [&](int i, const string &pat) {
                                   return s.substr(i, pat.length()) < pat;
                               }) -
                   sa.begin();

        int right = upper_bound(sa.begin(), sa.end(), pattern,
                                [&](const string &pat, int i) {
                                    return pat < s.substr(i, pat.length());
                                }) -
                    sa.begin();

        return {left, right};
    }
};

// 字符串工具函数
namespace StringUtils
{
// 字符串分割
vector<string> split(const string &s, const string &delimiter)
{
    vector<string> result;
    size_t start = 0, end = 0;

    while ((end = s.find(delimiter, start)) != string::npos) {
        result.push_back(s.substr(start, end - start));
        start = end + delimiter.length();
    }
    result.push_back(s.substr(start));

    return result;
}

// 字符串连接
string join(const vector<string> &strings, const string &delimiter)
{
    if (strings.empty())
        return "";

    string result = strings[0];
    for (size_t i = 1; i < strings.size(); ++i) {
        result += delimiter + strings[i];
    }
    return result;
}

// 去除前后空格
string trim(const string &s)
{
    size_t start = s.find_first_not_of(" \t\n\r");
    if (start == string::npos)
        return "";

    size_t end = s.find_last_not_of(" \t\n\r");
    return s.substr(start, end - start + 1);
}

// 转换为小写
string to_lower(const string &s)
{
    string result = s;
    transform(result.begin(), result.end(), result.begin(), ::tolower);
    return result;
}

// 转换为大写
string to_upper(const string &s)
{
    string result = s;
    transform(result.begin(), result.end(), result.begin(), ::toupper);
    return result;
}

// 字符串替换
string replace_all(string s, const string &from, const string &to)
{
    size_t pos = 0;
    while ((pos = s.find(from, pos)) != string::npos) {
        s.replace(pos, from.length(), to);
        pos += to.length();
    }
    return s;
}

// 检查是否为回文
bool is_palindrome(const string &s)
{
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}

// 最长公共前缀
string longest_common_prefix(const vector<string> &strings)
{
    if (strings.empty())
        return "";

    string prefix = strings[0];
    for (size_t i = 1; i < strings.size(); ++i) {
        while (strings[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.length() - 1);
            if (prefix.empty())
                return "";
        }
    }
    return prefix;
}

// 编辑距离
int edit_distance(const string &s1, const string &s2)
{
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; ++i)
        dp[i][0] = i;
    for (int j = 0; j <= n; ++j)
        dp[0][j] = j;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }

    return dp[m][n];
}

// 字符串匹配 (简单版本)
vector<int> find_all(const string &text, const string &pattern)
{
    vector<int> result;
    size_t pos = text.find(pattern, 0);
    while (pos != string::npos) {
        result.push_back(pos);
        pos = text.find(pattern, pos + 1);
    }
    return result;
}
} // namespace StringUtils

// 高级字符串操作工具
namespace StringOps
{
// 字符串转数字（支持各种类型）
template <typename T>
T string_to_number(const string &s)
{
    istringstream iss(s);
    T result;
    iss >> result;
    return result;
}

// 数字转字符串（支持格式化）
template <typename T>
string number_to_string(T num, int precision = -1)
{
    ostringstream oss;
    if (precision >= 0) {
        oss << fixed << setprecision(precision);
    }
    oss << num;
    return oss.str();
}

// 字符串填充（左填充）
string pad_left(const string &s, int width, char fill = ' ')
{
    if ((int)s.length() >= width)
        return s;
    return string(width - s.length(), fill) + s;
}

// 字符串填充（右填充）
string pad_right(const string &s, int width, char fill = ' ')
{
    if ((int)s.length() >= width)
        return s;
    return s + string(width - s.length(), fill);
}

// 字符串反转
string reverse_string(const string &s)
{
    string result = s;
    reverse(result.begin(), result.end());
    return result;
}

// 检查字符串是否为数字
bool is_number(const string &s)
{
    if (s.empty())
        return false;
    int start = 0;
    if (s[0] == '+' || s[0] == '-')
        start = 1;
    if (start >= (int)s.length())
        return false;

    bool has_dot = false;
    for (int i = start; i < (int)s.length(); i++) {
        if (s[i] == '.') {
            if (has_dot)
                return false;
            has_dot = true;
        } else if (!isdigit(s[i])) {
            return false;
        }
    }
    return true;
}

// 字符串重复
string repeat(const string &s, int count)
{
    string result;
    for (int i = 0; i < count; i++) {
        result += s;
    }
    return result;
}

// 字符串插入（在指定位置插入）
string insert_at(const string &s, int pos, const string &insert)
{
    if (pos < 0 || pos > (int)s.length())
        return s;
    return s.substr(0, pos) + insert + s.substr(pos);
}

// 字符串删除（删除指定范围）
string erase_range(const string &s, int start, int length)
{
    if (start < 0 || start >= (int)s.length())
        return s;
    if (length < 0)
        length = s.length() - start;
    return s.substr(0, start) + s.substr(start + length);
}

// 统计字符频率
map<char, int> count_chars(const string &s)
{
    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    return freq;
}

// 移除重复字符（保持顺序）
string remove_duplicates(const string &s)
{
    string result;
    unordered_set<char> seen;
    for (char c : s) {
        if (seen.find(c) == seen.end()) {
            seen.insert(c);
            result += c;
        }
    }
    return result;
}

// 字符串压缩（连续字符计数）
string compress(const string &s)
{
    if (s.empty())
        return s;

    string result;
    char current = s[0];
    int count = 1;

    for (int i = 1; i < (int)s.length(); i++) {
        if (s[i] == current) {
            count++;
        } else {
            result += current;
            if (count > 1) {
                result += to_string(count);
            }
            current = s[i];
            count = 1;
        }
    }

    result += current;
    if (count > 1) {
        result += to_string(count);
    }

    return result;
}
} // namespace StringOps

// 简单正则表达式风格的字符串匹配
namespace SimpleRegex
{
// 通配符匹配（支持 * 和 ?）
bool wildcard_match(const string &text, const string &pattern)
{
    int m = text.length(), n = pattern.length();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (pattern[j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (pattern[j - 1] == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (pattern[j - 1] == '?' || text[i - 1] == pattern[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

// 简单的字符串替换
string simple_replace(const string &text, const string &from, const string &to)
{
    string result = text;
    size_t pos = 0;
    while ((pos = result.find(from, pos)) != string::npos) {
        result.replace(pos, from.length(), to);
        pos += to.length();
    }
    return result;
}
} // namespace SimpleRegex
